package cn.edu.bjut.my.thinkinjava._20200501_02_DynamicProgram;

import java.util.ArrayList;

/**
 * 本例用于梳理动态规划思路
 * <p>
 * 题目：
 * 给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，
 * 问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
 * // coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 * 比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 * <p>
 * 思路：
 * 极值问题考虑动态规划
 * -是否含有子问题：含有子问题，将amount缩小
 * -子问题重复：子问题重复
 * -状态方程：f(amount,coins)=num
 * --状态:amount  也就是原问题和子问题中变化的变量
 * --选择:coins 种类 也就是对于每个状态，可以做出什么选择改变当前状态
 * --方程：dp(11)=1+Math.min(dp(10),dp(9),dp(6))
 */
public class _01CoinChange {
    private ArrayList dp = new ArrayList<Integer>();

//    public int coinChange(int[] coins, int n) {
//        if (n == 0) {
//            return 0;
//        } else if (n <= -1) {
//            return -1;
//        } else {
//            int res = Integer.MAX_VALUE;
//            for (int i = 0; i < 3; i++) {
//                int t = dp(n - coins[i], coins);
//                if (t == -1) continue;
//                res = Math.min(res, 1 + t);
//
//            }
//            return res;
//        }
////        return -1;
//    }

    private int dp(int n, int[] coins,int[] dp) {
        if (n == 0) {
            return 0;
        } else if (n <= -1) {
            return -1;
        } else {
            if(dp[n-1]!=0){
                System.out.println(n+"userd");
                return  dp[n-1];
            }
            int res = Integer.MAX_VALUE;
            for (int i = 0; i < 3; i++) {
                int t = dp(n - coins[i], coins,dp);
                if (t == -1) continue;
                res = Math.min(res, 1 + t);

            }
            System.out.println(n+"------>"+res);
            dp[n-1]=res;
            return res;
        }
    }

    public static void main(String[] args) {
        _01CoinChange coinChange = new _01CoinChange();
        int amount = 11;
        int[] coins = {1, 2, 5};
        int[] dp = new int[amount];
        int i = coinChange.dp(amount, coins,dp);
        System.out.println(i);
        for (int t:dp){
            System.out.print(t+"  ");
        }
    }
}
